package com.since.algorithm.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created by Sincerity on 2020/5/9.
 * 描述： 后缀表达式 (逆波兰表达式)
 * 1. 中缀字符串转为中缀数组{@link #infixToArrayList(String)}
 * 2. 中缀数组转为后缀数组{@link #infixToSuffix(List)}
 * 3. 计算后缀数组 {@link #calculationSuffixCalculation(List)}
 */
class SuffixExpression {
    public static void main(String[] args) {
        String expression = "1000";//8+4-6*2  2*(3+5)+7/1-4
        List<String> infix = infixToArrayList(expression);
        System.out.println("中缀字符串:" + infix);
        List<String> suffix = infixToSuffix(infix);
        System.out.println("后缀字符串:" + suffix);
        int sum = calculationSuffixCalculation(suffix);
        System.out.println("后缀表达式的值:" + sum);
    }

    /**
     * 通过后缀表达式计算
     * 从左至右扫描，将3和4压入堆栈；
     * 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
     * 将5入栈；
     * 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
     * 将6入栈；
     * 最后是-运算符，计算出35-6的值，即29，由此得出最终结果
     *
     * @param suffixExpression 后缀表达式[1000, 2, 3, +, 4, ×, +, 5, -]
     * @return 计算后的后缀表达式
     */
    private static int calculationSuffixCalculation(List<String> suffixExpression) {
        Stack<String> stack = new Stack<>();
        int num1, num2;
        for (String item : suffixExpression) {
            if (item.matches("\\d+")) {
                stack.push(item);
            } else {
                if (stack.size() >= 2) {
                    num1 = Integer.parseInt(stack.pop());
                    num2 = Integer.parseInt(stack.pop());
                    int sum = calculation(num1, num2, item);
                    stack.push(sum + "");
                } else {
                    stack.push(item);
                }

            }
        }
        while (stack.size() != 0 && stack.size() >= 3) {
            num1 = Integer.parseInt(stack.pop());
            String i = stack.pop();
            num2 = Integer.parseInt(stack.pop());
            stack.push(calculation(num1, num2, i) + "");

        }
        return Integer.parseInt(stack.pop());
    }

    /**
     * 计算表达式的结果
     *
     * @param num1 数字1
     * @param num2 数字2
     * @param per  运算符
     */
    private static int calculation(int num1, int num2, String per) {
        int res;
        switch (per) {
            case "+":
                res = num1 + num2;
                break;
            case "-":
                res = num2 - num1;
                break;
            case "*":
                res = num1 * num2;
                break;
            case "/":
                res = num2 / num1;
                break;
            default: {
                throw new RuntimeException("运算符不存在");
            }
        }
        return res;
    }

    /**
     * 中缀字符串转为后缀字符串
     * 1.初始化两个栈：运算符栈s1和储存中间结果的栈s2(逆序输出的话可以使用ArrayList)；
     * 2.从左至右扫描中缀表达式；
     * 3.遇到操作数时，将其压s2；
     * 4.遇到运算符时，比较其与s1栈顶运算符的优先级：
     * 4.1.如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
     * 4.2.否则，若优先级比栈顶运算符的高，也将运算符压入s1；
     * 4.3.否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
     * 5.遇到括号时：  (1) 如果是左括号“(”，则直接压入s1 (2) 如果是右括号“)”，
     * 则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
     * 6.重复步骤2至5，直到表达式的最右边
     * 7.将s1中剩余的运算符依次弹出并压入s2
     * 8.依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
     *
     * @param infixArray 中缀数组
     * @return 返回一个后缀数组
     */
    private static List<String> infixToSuffix(List<String> infixArray) {
        //1.初始化两个栈：运算符栈s1和储存中间结果的栈s2(逆序输出的话可以使用ArrayList)；
        Stack<String> stack = new Stack<>();
        ArrayList<String> stack2 = new ArrayList<>();
        //从左至右扫描中缀表达式；
        for (String ch : infixArray) {
            //遇到操作数时，将其压s2；
            if (ch.matches("^[-\\+]?[.\\d]*$")) {
                stack2.add(ch);
            } else if (ch.equals(".")) {
                //
            } else if (ch.equals("(")) {
                //遇到括号时：  (1) 如果是左括号“(”，则直接压入s1
                stack.push(ch);
            } else if (ch.equals(")")) {
                //(2) 如果是右括号“)”则依次弹出s1栈顶的运算符并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
                //[1000, +, (, (, 2, +, 3, ), ×, 4, ), -, 5]
                while (!stack.peek().equals("(")) {
                    stack2.add(stack.pop());
                }
                stack.pop();
            } else {
                //遇到运算符时，比较其与s1栈顶运算符的优先级
                //4.1.如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
                if (stack.empty() || stack.peek().equals("(")) {
                    stack.push(ch);
                } else {
                    //否则，若优先级比栈顶运算符的高，也将运算符压入s1；
                    if (priority(ch) > priority(stack.peek())) {
                        stack.push(ch);
                    } else {
                        // 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
                        //二个运算符优先级相同的时候也要考虑
                        while (stack.size() != 0 && priority(ch) <= priority(stack.peek())) {
                            stack2.add(stack.pop());
                        }
                        stack.push(ch);
                    }
                }
            }
        }
        //将s1中剩余的运算符依次弹出并压入s2
        while (stack.size() != 0) {
            stack2.add(stack.pop());
        }

        return stack2;

    }

    /**
     * 将中缀转化成字符串
     *
     * @param expression 字符串 1+((2+3)×4)-5
     * @return 中缀字符串数组  1 2 3 + 4 × + 5 –"
     */
    private static List<String> infixToArrayList(String expression) {
        String newExpression = expression.replaceAll("\\s+", "");
        ArrayList<String> list = new ArrayList<>();
        char c, c1;
        String nums;
        for (int i = 0; i < newExpression.length(); i++) {
            c = newExpression.substring(i, i + 1).charAt(0);
            //非数字
            if (c < 48 || c > 57) {
                list.add(c + "");
            } else {
                if (i < newExpression.length() - 1) {
                    nums = "";
                    nums += c;
                    for (int j = i + 1; j < newExpression.length(); j++) {
                        c1 = newExpression.substring(j, j + 1).charAt(0);
                        if (c1 >= 48 && c1 <= 57) {
                            nums += c1;
                            i++;
                        } else {
                            break;
                        }

                    }
                } else {
                    nums = String.valueOf(c);
                }

                list.add(nums);
            }
        }
        return list;
    }

    /**
     * 自定义运算符的优先级 + - 默认为0 * / 默认为1
     *
     * @param value 运算符
     * @return 优先级
     */
    private static int priority(String value) {
        int res;
        if (value.equals("+") || value.equals("-")) {
            res = 0;
        } else if (value.equals("*") || value.equals("/")) {
            res = 1;
        } else {
            res = -1;
        }
        return res;
    }
}
